#pragma once

template<typename T>
class RandomList
{
public:
	template<typename T>
	struct suData
	{
		suData() { m_iNext = m_iPre = -1; }
		T m_data;
		int m_iNext, m_iPre;
	};
public:
	typedef typename std::vector<suData<T>>::iterator Iterator;
	typedef int ID;
public:
	bool IsValidID(ID id)
	{
		if (m_NotUse.find(id) != m_NotUse.end())return false;
		if (id > 0 && id < m_vData.size())return true;
		return false;
	}

	void Clear()
	{
		m_NotUse.clear();
		m_vData.clear();
		m_iNext = m_iPre = -1;
	}

	void Erase(Iterator pos)
	{
		int idPos = pos - m_vData.begin();
		if (m_NotUse.find(idPos) != m_NotUse.end()) return;
		if (pos->m_iNext == idPos)
		{
			Clear();
		}
		else
		{
			RandomList::Iterator posPre, posNext;
			posPre = m_vData.begin() + pos->m_iPre;
			posNext = m_vData.begin() + pos->m_iNext;
			posPre->m_iNext = pos->m_iNext;
			posNext->m_iPre = pos->m_iPre;
			m_NotUse.insert(idPos);
		}
	}

	void InsertData(Iterator pos, T data, bool IsInsertPre = true)
	{
		suData d;
		d.m_data = data;
		int idPos = pos - m_vData.begin();
		int idNow;
		if (m_NotUse.empty())
		{
			idNow = m_vData.size();
			m_vData.push_back(d);
		}
		else
		{
			idNow = *(m_NotUse.begin());
			m_NotUse.erase(m_NotUse.begin());
		}
		if (IsInsertPre)
		{
			d.m_iPre = pos->m_iPre;
			d.m_iNext = idPos;
			if (pos->m_iPre >= 0)
			{
				m_vData[pos->m_iPre].m_iNext = idNow;
			}
			pos->m_iPre = idNow;
			if (idPos == m_idFirst)m_idFirst = idNow;
		}
		else
		{
			d.m_iPre = idPos;
			d.m_iNext = idPos->m_iNext;
			if (pos->m_iNext >= 0)
			{
				m_vData[pos->m_iNext].m_iPre = idNow;
			}
			pos->m_iNext = idNow;
			if (idPos == m_idLast)m_idLast = idNow;
		}
		m_vData[idNow] = d;
	}

	void Push(T data)
	{
		if (m_idFirst == -1 || m_idLast == -1)
		{
			int idNow;
			if (m_NotUse.empty())
			{
				idNow = m_vData.size();
				m_vData.push_back(suData());
			}
			m_vData[idNow].m_data = data;
			m_vData[idNow].m_iNext = m_vData[idNow].m_iPre = idNow;
			m_idFirst = m_idLast = idNow
		}
		else
		{
			InsertData(m_vData.begin() + m_idLast, data, false);
		}
	}

	void PushFirst(T data)
	{
		if (m_idFirst == -1 || m_idLast == -1)
		{
			int idNow;
			if (m_NotUse.empty())
			{
				idNow = m_vData.size();
				m_vData.push_back(suData());
			}
			m_vData[idNow].m_data = data;
			m_vData[idNow].m_iNext = m_vData[idNow].m_iPre = idNow;
			m_idFirst = m_idLast = idNow
		}
		else
		{
			InsertData(m_vData.begin() + m_idFirst, data, true);
		}
	}

	Iterator GetPos(ID id)
	{
		if (!IsValidID(id))return m_vData.end();
		return m_vData.begin() + id;
	}

	ID GetID(Iterator pos)
	{
		ID id = pos - m_vData.begin();
		if (!IsValidID(id))id = -1;
		return id;
	}

	Iterator Begin()
	{
		if (m_idFirst == -1)
		{
			return m_vData.end();
		}
		return m_vData.begin() + m_idFirst;
	}

	Iterator End()
	{
		if (m_idLast == -1)
		{
			return m_vData.end();
		}
		return m_vData.begin() + m_idLast;
	}

	Iterator Plus(const Iterator& pos)
	{
		int idNext = pos->m_iNext;
		return m_vData.begin() + idNext;
	}

	ID GetNextID(ID id)
	{
		Iterator pos = GetPos(id);
		pos = Plus(pos);
		return GetID(pos);
	}

	T GetData(ID id)
	{
		return m_vData[id].m_data;
	}
protected:
	vector<suData<T>> m_vData;
	int m_idFirst, m_idLast;
	unordered_set<int> m_NotUse;
};